/*
Network Design Project
"Minimum Bound Degree Spanning Tree"
Version: 0.4
Authors: Alessandro Baroni, Paolo Bozzelli, Giuseppe Cascavilla
Domain: univaq.it
*/

#define USAGE "mbdst-formulation.out <min_n> <max_n> <min_w> <max_w> <k>\n"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <glpk.h>
#include "lib/ourlib.h"

int main(int argc,char *argv[]) {

	glp_graph *G;
	glp_prob *lp;
	glp_arc *arcp;
	// Bound sulle istanze
	int min_n, max_n, min_w, max_w, current;
	char varname[15];
	const char* CONSTRAINT_TEMPLATE = "bounded degree constraint for node %d";
	const char* ARC_TEMPLATE = "x_%d_%d";
	char constraint_name[128];
	char arc_name[128];
	int na, nv, i, a, arc_count = 0, k;
	int ia[1+1000], ja[1+1000];
	double ar[1+1000], z, *x;

	// Bounded Degree
	switch (argc) {
		default:
		case 0:
		case 1:
		case 2:
		case 3:
		case 4:
		case 5:
			printf(USAGE);
			return -1;
			break;
		case 6: 
			// TODO controlli su consistenza valori
			min_n = atoi(argv[1]);
			max_n = atoi(argv[2]);
			min_w = atoi(argv[3]);
			max_w = atoi(argv[4]);
			
			if (atoi(argv[5]) > max_n) {
				k = max_n - 1;
			} else {
				k = atoi(argv[5]);
			}
			
			break;
	}
	
	// Inizializzazione variabili
	strcpy(varname, "");

	G = custom_create_graph();
	G = random_graph_v2(min_n, max_n, min_w, max_w);
	
	na = get_number_of_arcs(G);
	nv = get_number_of_nodes(G);
	x = malloc(sizeof(double) * na);
	
	printf("Numero di archi: %d\nNumero di nodi: %d\n", get_number_of_arcs(G), get_number_of_nodes(G));
	
	custom_write_graph(G, "generated_graph.txt");

	// Creazione del problema
	lp = glp_create_prob();
	glp_set_prob_name(lp, "Formulazione incompleta");
	
	// Tipo (direzione) del problema
	glp_set_obj_dir(lp, GLP_MIN);
	
	// Aggiungo righe
	// nv+1 = vincoli di bound degree sui nodi + vincolo di spanning tree
	glp_add_rows(lp, nv+1);

	// Inizializzazione delle righe
	glp_set_row_name(lp, 1, "Spanning constraint");
	glp_set_row_bnds(lp, 1, GLP_FX, nv-1, nv-1);
	
	// Aggiungo colonne
	glp_add_cols(lp, na);
	
	// Inizializzazione delle colonne
	for(i = 1; i <= nv; i++){
		arcp = G->v[i]->out;
		//printf("%d\n",get_node_degree(G,i)); 
		while (arcp != NULL) {
			arc_count++;
			generate_arc_name(arcp, varname);
			glp_set_col_name(lp, arc_count, varname);
			glp_set_col_bnds(lp, arc_count, GLP_DB, 0.0, 1.0);
			glp_set_obj_coef(lp, arc_count, get_arc_w(arcp)); // Aggiungo peso dell'arco come coefficiente della variabile correlata
			arcp = arcp->t_next;
		}
	}
	
	for (a = 0; a < glp_get_num_cols(lp); a++) {
		ia[a+1] = 1;
		ja[a+1] = a+1;
		ar[a+1] = 1;
		current = a+1;
	}
	
	// nv righe del problema per bounded degree
	for (i = 2; i <= (nv+1); i++) {
		sprintf(constraint_name,CONSTRAINT_TEMPLATE,i-1);
		glp_set_row_name(lp, i, constraint_name);
		glp_set_row_bnds(lp, i, GLP_UP, 0.0, k);
	}
	
	// Generazione dell'indice delle variabili
	glp_create_index(lp);
	
	for (i = 1; i <= nv; i++) {
		// Per ogni nodo
		arcp = G->v[i]->out;
		while (arcp != NULL) {
			// Per ogni arco uscente
			current++;
			ia[current] = i+1;			// Dalla riga 2 in poi (prima riga occupata dallo ST)
			sprintf(arc_name,ARC_TEMPLATE,arcp->tail->i, arcp->head->i);
			ja[current] = glp_find_col(lp, arc_name);
			ar[current] = 1.0;
			arcp = arcp->t_next;
		}
		
		arcp = G->v[i]->in;
		while (arcp != NULL) {
			// Per ogni arco uscente
			current++;
			ia[current] = i+1;			// Dalla riga 2 in poi (prima riga occupata dallo ST)
			sprintf(arc_name,ARC_TEMPLATE,arcp->tail->i, arcp->head->i);
			ja[current] = glp_find_col(lp, arc_name);
			ar[current] = 1.0;
			arcp = arcp->h_next;
		}
		
		
	} 
	
	printf("Vettori del problema:\n");
	for (a = 0; a < current; a++) {
		printf("ia[%d] = %d;\tja[%d] = %d;\tar[%d] = %lf.\n", a+1, ia[a+1], a+1, ja[a+1], a+1, ar[a+1]);
	}
	
	glp_load_matrix(lp, current, ia, ja, ar);
	
	glp_write_lp(lp, NULL, "mbdst-formulation.lp");
	
	glp_simplex(lp, NULL);
	
	int final_solution_arcs = 0;

	z = glp_get_obj_val(lp);
	for (i = 0; i < glp_get_num_cols(lp); i++) {
		x[i] = glp_get_col_prim(lp, i+1);
		if (x[i] == 1) {
			final_solution_arcs++;
		}
	}

	// Stampa su stdout del risultato
	printf("\nObjective:\tz = %g;\n", z);
	printf("Vector:\n");
	for (i = 0; i < glp_get_num_cols(lp); i++) {
		//printf("\tx%d = %g;\n", i+1, x[i]);
		printf("\t\t%s = %g\n", glp_get_col_name(lp, i+1), x[i]);
	}
	
	printf("La soluzione finale ha %d archi.\n", final_solution_arcs);
	
	custom_write_sol(G,lp,"soluzione");
	//printf("File scritto con successo. Spero.\n");
	glp_delete_prob(lp);
	custom_delete_graph(G);

	return 0;

}
